package 中等.贪心思想;

import java.util.Arrays;

/**
 * 给定字符串列表 strs ，返回其中 最长的特殊序列 。如果最长特殊序列不存在，返回 -1 。
 * 特殊序列 定义如下：该序列为某字符串 独有的子序列（即不能是其他字符串的子序列）。
 *  s 的 子序列可以通过删去字符串 s 中的某些字符实现。
 * 例如，"abc" 是 "aebdc" 的子序列，因为您可以删除"aebdc"中的下划线字符来得到 "abc" 
 * 。"aebdc"的子序列还包括"aebdc"、 "aeb" 和 "" (空字符串)。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/longest-uncommon-subsequence-ii
 */
public class 最长特殊序列II_522 {

    public static void main(String[] args) {

        String[] strs = {"aaa", "aaa", "aa"};
        System.out.println(new 最长特殊序列II_522().findLUSlength(strs));

    }

    /**
     * 如果某个字符串的子序列为特殊序列，那么整个字符串也是特殊序列，
     * 贪心取整个字符串的长度，如果整个字符串不是其他字符串的子序列，
     * 那么这个字符串就是一个特殊序列
     * 如果长度最长的字符串只有一个，那么把它当成子序列即为答案，
     *
     * @param strs
     * @return
     */
    public int findLUSlength(String[] strs) {
        // 贪心将字符串长度长的排前面
        Arrays.sort(strs, (o1, o2) -> o2.length() - o1.length());
        for (int i = 0; i < strs.length; i++) {
            String str1 = strs[i];
            boolean flag = true;
            for (int j = 0; j < strs.length; j++) {
                if (j == i) continue;
                if (isChildStr(str1, strs[j])) {
                    flag = false;
                    break;
                }
            }
            if (flag) return str1.length();
        }
        return -1;
    }

    private boolean isChildStr(String childStr, String parentStr) {
        if (childStr.length() > parentStr.length()) return false;
        int cIdx = 0, pIdx = 0;
        while (pIdx < parentStr.length() && cIdx < childStr.length()) {
            if (childStr.charAt(cIdx) == parentStr.charAt(pIdx)) {
                cIdx++;
            }
            pIdx++;
        }
        return cIdx == childStr.length();
    }

}
